package list;

public class MiddleNode {
    public static void main(String[] args) {
        Node head = new Node(7);
        head.next = new Node(3);
        head.next.next = new Node(8);
        head.next.next.next = new Node(5);
        head.next.next.next.next = new Node(6);
        head.next.next.next.next.next = new Node(9);

        Node mid = middleNode(head);
        System.out.println(mid.value);

        //遍历节点
//        Node n = head; //从头部节点开始访问
//        while (n != null) { //只要引用了节点就继续访问节点数据
//            System.out.println(n.value); //访问节点中的数据
//            n = n.next; //得到n后面的节点，保存到n
//        }
    }

    public static Node middleNode(Node head) {
        Node fast = head; //快引用，引用头部节点
        Node slow = head; //慢引用，引用头部节点

        //fast在范围内并且它的下一个也不是null
        while (fast != null && fast.next != null) {
            fast = fast.next.next; //fast向后引用下两个节点
            slow = slow.next; //slow向后引用下一个节点
        }

        return slow; //slow所引用的节点，就是中间节点
    }

    static class Node {
        private int value;
        private Node prev;
        private Node next;

        public Node(int value) {
            this.value = value;
        }
    }
}
